'''
https://leetcode.cn/problems/parallel-courses-iii/description/
'''
from collections import defaultdict, deque
from typing import List


class Solution:

    def minimumTime(self, n: int, relations: List[List[int]], time: List[int]) -> int:
        graph = defaultdict(list)
        indegrees = [0] * n
        for u, v in relations:
            graph[u - 1].append(v - 1)
            indegrees[v - 1] += 1
        q = deque()
        end_less_time = [0] * n  # 修完i门课最少需要多久
        for i, indegree in enumerate(indegrees):
            if indegree == 0:
                q.append(i)
                end_less_time[i] = time[i]
        ans = 0
        while q:
            u = q.popleft()
            if graph[u]:
                for v in graph[u]:
                    if end_less_time[u] + time[v] > end_less_time[v]:
                        end_less_time[v] = end_less_time[u] + time[v]
                    indegrees[v] -= 1
                    if indegrees[v] == 0:
                        q.append(v)
            else:
                ans = max(ans, end_less_time[u])
        return ans
